import java.util.ArrayList;
import java.util.List;

class MedianFinder {
    List<Integer> sortArr;

    public MedianFinder() {
        sortArr = new ArrayList<>();
    }

    private int binarySearch(int target){
        int left = 0, right = sortArr.size()-1;
        while(left <= right){
            int mid = left + (right - left)/2;
            int tmpNum = sortArr.get(mid);
            if(tmpNum == target){
                return mid;
            }
            else if(target < tmpNum){
                right = mid - 1;
            }
            else{
                left = mid + 1;
            }
        }
        return left;
    }

    public void addNum(int num) {
        int loc = binarySearch(num);
        sortArr.add(loc, num);
    }

    public double findMedian() {
        int tmpSize = sortArr.size();
        if((tmpSize&1) == 1){
            return sortArr.get(tmpSize>>1);
        }
        return ((float)(sortArr.get((tmpSize>>1)-1) + sortArr.get(tmpSize>>1)))/2;
    }
}
